import java.util.Arrays;

/**
 * @Author: code.rookie
 * @ClassName: CoinChange
 * @PACKAGE_NAME: PACKAGE_NAME
 * @Version: 1
 */
public class CoinChange {
    public int coinChange(int[] coins, int amount) {
        int max = amount + 1;
        int[] dynamicPlan = new int[max];
        Arrays.fill(dynamicPlan, max);
        dynamicPlan[0] = 0;
        for(int f1 = 1; f1 <= amount; f1++) {
            for(int f2 = 0; f2 < coins.length; f2++) {
                if(coins[f2] <= f1) {
                    dynamicPlan[f1] = Math.min(dynamicPlan[f1], dynamicPlan[f1 - coins[f2]] + 1);
                }
            }
        }

        int result = dynamicPlan[amount] > amount ? -1 : dynamicPlan[amount];
        return result;
    }
}
